For the design of digital circuits (e.g., on the scale of Very Large Scale Integration (VLSI) technology), designers often employ computer aided techniques. Standard languages such as Hardware Description Languages (HDLs) have been developed to describe digital circuits to aid in the design and simulation of complex digital circuits. Several hardware description languages, such as VHDL and Verilog, have evolved as industry standards. VHDL and Verilog are general purpose hardware description languages that allow definition of a hardware model at the gate level, the register transfer level (RTL) or the behavioral level using abstract data types. As device technology continues to advance, various product design tools have been developed to adapt HDLs for use with newer devices and design styles.
In designing an integrated circuit with an HDL code, the code is first written and then compiled by an HDL compiler. The HDL source code describes at some level the circuit elements, and the compiler produces an RTL netlist from this compilation. The RTL netlist is typically a technology independent netlist in that it is independent of the technology/architecture of a specific vendor's integrated circuit, such as field programmable gate arrays (FPGA) or an application-specific integrated circuit (ASIC). The RTL netlist corresponds to a schematic representation of circuit elements (as opposed to a behavioral representation). A mapping operation is then performed to convert from the technology independent RTL netlist to a technology specific netlist which can be used to create circuits in the vendor's technology/architecture. It is well known that FPGA vendors utilize different technology/architecture to implement logic circuits within their integrated circuits. Thus, the technology independent RTL netlist is mapped to create a netlist which is specific to a particular vendor's technology/architecture.
One operation, which is often desirable in this process, is to plan the layout of a particular integrated circuit and to control timing problems and to manage interconnections between regions of an integrated circuit. This is sometimes referred to as “floor planning.” A typical floor planning operation divides the circuit area of an integrated circuit into regions, sometimes called “blocks,” and then assigns logic to reside in a block. These regions may be rectangular or non-rectangular. This operation has two effects: the estimation error for the location of the logic is reduced from the size of the integrated circuit to the size of the block (which tends to reduce errors in timing estimates), and the placement and the routing typically runs faster because as it has been reduced from one very large problem into a series of simpler problems.
Significant optimization efforts have been devoted to assignment of resources and resource utilization. Circuit level optimization contributes significantly to the optimum design, including circuitry modification and re-placement to achieve desired timing and desired area. For example, circuit placement related optimizations include adder tree or gate decomposition, logic replication, bit slicing and detour removal.
In addition, advances in data flow programs for digital signal processing has provided significant progress in circuit optimization using data flow graphs, especially for parallel computers. A data flow graph representation is a popular hardware and software methodology where algorithms are described as directed graphs with nodes representing computations (or functions or subtasks) and edges representing data paths (communications between nodes) Data flow algorithm is mainly concerned with the flow of data and not with the actual computation process, and is a natural paradigm for describing digital signal processing applications for concurrent implementation on parallel hardware. For concurrent implementations, a task is broken into subtasks which are then scheduled onto parallel processors.
For example, FIG. 1A illustrates a circuit block diagram describing the computation y[n]=ay[n−1]+x[n]. This is a feedback function where the computational output y[n] depends on the value of its previous output y[n−1]. The block diagram shows a delay block D, which can be a delay register, to store the previous value of the output y. A multiplication block X is provided to multiply the delay output y[n−1] and a constant a. An addition block+is provided to add the input x[n] with the multiplied delay output ay[n−1]. A key feature of a circuit block diagram is that the functionality of the circuit can be understood and derived from the circuit block diagram. For example, the computation y[n]=ay[n−1]+x[n] can be calculated from the circuit block diagram of FIG. 1A at a circuit operation level.
FIG. 1B illustrates a data flow graph of this block diagram with node A representing the addition block and node B representing the multiplication block. The edge from B to A (B→A) represents the data path from the multiplication block to the addition block, and the edge from A to B (A→B) represents the data path from the addition block to the multiplication block. The delay D is inserted to the data path from A to B to show that the edge from A to B (A→B) contains one delay (e.g., 1 clock cycle delay). The input branch x[n] and the output branch y[n] are shown in dotted lines, mainly for an illustration of the correlation with the block diagram of FIG. 1A. In practice, the input and output branches are typically not shown in a data flow graph (e.g., FIG. 1C). Alternatively, the delay D can be shown in the vicinity of the edge (FIG. 1C).
Other information can be included in the data flow graph, for example, information related to synchronous data flow graph to show that execution of nodes A and B consumes one data sample and produces output. This is illustrated by a number 1 from the edge coming to node A/B and a number 1 from the edge coming out of node A/B. Each node can have an execution time associated with it, for example, the amount of time required to execute node A (addition computation) is 2 time units (e.g., 2 clock cycles), and the amount of time required to execute node B (multiplication computation) is 4 time units. This is illustrated by a number in parentheses (2) and (4) in the vicinity of nodes A and node B, respectively.
Typically, operations of a data flow graph at a data flow level are operations related only to the data flow without regard to functional or computational operations. For example, the critical path of a data flow graph is defined to be the path with the longest computation time among all paths that contain zero delay. Thus the critical path in the data flow graph shown in FIG. 1B is the path B→A, which requires 6 time units. Optimizing the critical path is an example of optimizing a data flow graph at a data flow level.
The illustrated data flow graph describes a single rate system where all nodes consume one data sample and produce one output relative to a clock cycle. In multirate systems, the number of data samples consumed and produced can be different than 1, such as in a system where the nodes operate at different frequencies or a decimator or an interpolator. For example, a ↓2 decimator rejects every other data sample, thus producing one data output for every 2 data samples consumed. A ↑2 interpolator introduces an addition data output for every data sample, thus producing ↑2 data outputs for every 1 data sample consumed.
In addition to being natural to digital signal processing, a data flow graph representation has another advantage of generating the same results for any implementations of the data flow description, as long as the integrity of the flow of data is preserved. Thus data flow graph representations can be an indispensable tool in scheduling and mapping circuit design representation onto hardware. The current data flow graph representations employ nodes and edges, together with using linear programming to optimize the flow of data to achieve a desired clock. Information related to actual circuitry is not relevant and in general, no longer presented in the data flow graph representations.